import java.util.Arrays;

public class Heapsort {

}
class HeapSort{
    public static int[] sortArray(int[] a) {
        heapify(a, a.length);
        for (int right = a.length-1; right > 0; right--){
            swap(a, 0, right);
            down(a, 0, right);
        }
        return a;
    }

    public static void heapify(int[] arr, int size){
        for (int i = size / 2 - 1; i>=0; i--){
            down(arr, i, size);
        }
    }

    private static void down(int[] arr, int parent, int size){
        while (true){
            int left = parent * 2 + 1;
            int right = left + 1;
            int max = parent;
            if (left < size && arr[left] > arr[max]){
                max = left;
            }
            if (right < size && arr[right] > arr[max]){
                max = right;
            }
            if (max == parent){
                break;
            }
            swap(arr, max, parent);
            parent = max;
        }
    }
    private static void swap(int[] arr, int i, int j){
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
    public static void main(String[] args) {
        int[] a = {2, 3, 1, 7, 6, 4, 5};
        System.out.println(Arrays.toString(a));
        sortArray(a);
        System.out.println(Arrays.toString(a));
    }
}